Spatial Simulations
Spatial simulation is a computer application that attempts to discover or experience the properties of a three-dimensional (3D) environment entirely within the computer. Simulated environments can be tested and improved before the actual environment is constructed. A few examples of this type of simulation are: walking through a building before it is constructed to determine if it is ergonomically correct; testing a factory assembly line for throughput and connect location of equipment and materials; construction of a airplane to see if all the parts fit together and testing for adequate room for each passenger; and testing a submarine design to determine if the crew can perform their necessary duties in the cramp space. This type of application of spatial simulation may require real time interaction with objects in the simulated environment and/or real time generation of the visual presentation.
Another need for spatial simulations is situated learning. Situated learning puts a pupil or trainee into a working environment in order to learn by experience. Simulation is important in situated learning because: 1) unusual or dangerous situations can be experienced easily and safely; 2) the actual environment may not exist or is not available for training; and 3) new teacher-trainee interaction can include things which maybe impossible in the actual environment (e.g., the teacher and pupil located in the same small physical space). This type of application of spatial simulation generally requires real time interaction with objects in the simulated environment and real time picture generation. A real time simulation of this type is sometimes called Virtual Reality (VR).
Simulation is also important in interactive entertainment. Interactive entertainment could include flying a simulated airplane or fighting a 3D dragon. This type of application generally requires real time interaction with objects and real time picture generation.
One major difficulty with spatial simulations is managing the vast amount of spatial data and determining object interactions. Determining object interactions is commonly called "collision detection". A simulation may include thousands of objects, many of which are moving. During the simulation, these objects can collide with other objects, causing objects to change trajectory, break into smaller objects, or merge to form larger objects. As an object's position changes during the simulation, its volume and/or surface must be compared to the volume and/or surface of the other objects. The set of objects form a spatial database and spatial queries are done using a moving object's volume and/or surface as the query region for the spatial query. In essence, a spatial query asks: does anything stored in the database occupy any part of the query region.
Spatial simulations are generally done in discrete time steps, where the state of the simulated environment is determined for particular instants in simulated time. During a simulation step, the time index is incremented by the time step, and a new state of the simulated environment is determined. In some simulations, the size of the time step can vary, depending on the rate of change of the state in the simulated environment. For example, time steps can be made smaller if objects in the simulation are moving faster.
Three-dimensional Computer Graphics
Spatial simulations usually include a visual presentation, generally done in real time, done with 3D computer graphics. Computer graphics is the art and science of generating pictures with a computer. Generation of pictures is commonly called rendering. Generally, in 3D computer graphics, geometry that represents surfaces (or volumes) of objects in a scene is translated into pixels stored in a frame buffer, and then displayed on a display device, such as a CRT.
A summary of the rendering process can be found in: "Fundamentals of Three-dimensional Computer Graphics", by Watt, Chapter 5: The Rendering Process, pages 97 to 113, published by Addison-Wesley Publishing Company, Reading, Mass., 1989, reprinted 1991, ISBN 0-201-15442-0 (hereinafter referred to as the Watt Reference).
An example of a hardware renderer is incorporated herein by reference: "Leo: A System for Cost Effective 3D Shaded Graphics", by Deering and Nelson, pages 101 to 108 of SIGGRAPH 93 Proceedings, 1-6 Aug. 1993, Computer Graphics Proceedings, Annual Conference Series, published by ACM SIGGRAPH, New York, 1993, Softcover ISBN 0-201-58889-7 and CD-ROM ISBN 0-201-56997-3 (hereinafter referred to as the Deering Reference).
In computer graphics, each renderable object generally has its own local object coordinate system, and therefore needs to be translated from object coordinates to pixel display coordinates. Conceptually, this is a 4-step process: 1) translation (including scaling for size enlargement or shrink) from object coordinates to world coordinates, which is the coordinate system for the entire scene; 2) translation from world coordinates to eye coordinates, based on the viewing point of the scene; 3) translation from eye coordinates to perspective translated eye coordinates, where perspective scaling (farther objects appear smaller) has been performed; and 4) translation from perspective translated eye coordinates to pixel coordinates, also called screen coordinates. These translation steps can be compressed into one or two steps by precomputing appropriate translation matrices before any translation occurs.
The input to the graphics pipeline is renderable geometry, generally in object coordinates. The renderable geometry is usually described by planar polygons, read from a graphics geometry database. For spatial simulations, it may be advantageous for the spatial data used for object interaction to be the same as the data used for rendering. This eliminates the need to generate two models (i.e., one for rendering and one for spatial interaction) for each object, and also eliminates the need to maintain two different databases as the spatial simulation proceeds.
FIG. 1 shows a three-dimensional object, a tetrahedron, with its own coordinate axes (x.sub.obj, y.sub.obj, z.sub.obj), hereinafter called object coordinates. The three-dimensional object 102 is translated, scaled, and placed in the viewing point's 104 coordinate system based on (x.sub.eye, y.sub.eye, z.sub.eye), called eye coordinates. The object 106 is projected onto the viewing plane 108, thereby correcting for perspective. At this point, the object appears to have become two-dimensional; however, the object's z-coordinates are preserved so they can be used later for hidden surface removal techniques. The object is finally translated to screen coordinates of the display screen 110, based on (x.sub.screen, y.sub.screen, z.sub.screen), where z.sub.screen is going perpendicularly into the page. Points on the object's surface now have their x and y coordinates described by pixel location within the display screen 110 and their z coordinates in a scaled version of distance from the viewing point. In a spatial simulation, object interaction computations are generally done in world coordinates, which has a fixed origin, and both simulated objects and the viewing point move relative to this origin.
Existing hardware renders take geometry in object coordinates and generate a set of pixel color values. The graphics pipeline smashes each polygon into individual pixels and does not keep any intermediate data. Because of this, computations for spatial interactions are not done within existing graphics pipelines. Since graphics pipelines do not keep any spatial data in world coordinates, rendered objects can pass through each other unless an additional spatial interaction process prevents it.
3D Graphics Geometry Databases
The geometry needed to generate a renderable scene is stored in a database (also called a data structure). This geometry database can be a simple display list of graphics primitives or a hierarchically organized data structure. In the hierarchically organized geometry database, the root of the hierarchy is the entire database, and the first layer of nodes in the data structure is generally all the objects in the "world" which can be seen from the viewpoint. Each object, in turn, contains subobjects, which, in turn, contain sub-subobjects; thus resulting in a hierarchical "tree" of objects. At the lowest level of the tree (here, trees grow downward) are the renderable primitives.
Hereinafter, the term "object" shall refer to any node in the hierarchial tree which is neither a renderable primitive nor the root of the entire scene. The term "root object" shall refer to a node in the first layer of nodes below the root in the data structure ("children" of the scene root node). The term "leaf object" will be used here to mean an node which has any child nodes that are renderable primitives. As illustrated in FIG. 2, the hierarchical database for a scene starts with the scene root node, then the first layer of nodes are the root objects, lower nodes are additional hierarchical objects, and any object that has a renderable primitive (in the figure, a polygon) as a child is a leaf object. Leaf objects can also have children that are other objects. An example of a leaf object that also has child objects is the upper arm portion of a robot arm. The upper arm has its own surface (and therefore has polygons as children), but also has the lower arm as a child (the lower arm is itself an object). Also, a root object can also be a leaf object.
Hierarchical databases are used by the Programmer's Hierarchical Interactive System (PHIGS) and PHIGS PLUS standards. An explanation of these standards can be found in the book, "A Practical Introduction to PHIGS and PHIGS PLUS", by T. L. J. Howard, et. al., published by Addison-Wesley Publishing Company, 1991, ISBN 0-201-41641-7 (incorporated herein by reference and hereinafter called the Howard Reference). The Howard Reference describes the hierarchical nature of 3D models and their data structure on pages 5 through 8.
Another type a data structure is the Binary Space Partitioning (BSP) Tree. BSP Trees presort the geometry by recursively subdividing space into two regions. A short tutorial on the subject can be found in: "Binary Space Partitioning Trees, A Tutorial", by Bruce Naylor, included in the course notes "Computational Representations of Geometry", Course 23, ACM SIGGRAPH 94, Jul. 24-29, 1994. In general, BSP Trees are best suited to rendering acceleration of static databases (no moving objects).
Spatial Databases and Spatial Querying
Spatial databases have many applications, and a serious exploration of these applications is found in "Applications of Spatial Data Structures", by H. Samet, published by Addison-Wesley Publishing Company, 1990, ISBN 0-201-50300-X.
Theoretical basis of spatial databases can be found in: 1) "Multi-dimensional Searching and Computational Geometry", by K. Melhorn, published by Springer-Verlag, 1984, ISBN 0-387-13642-8, hereinafter called the Melhorn Reference; 2) "Geographic Database Management Systems", Workshop Proceedings Capri, Italy, May 1991, edited by G. Gambosi, et. al., published by Springer-Verlag, 1992, ISBN 0-387-5561-6, hereinafter called the Gambosi Reference; and 3) "The Design and Analysis of Spatial Data Structures", by H. Samet, published by Addison-Wesley Publishing Company, 1989, ISBN 0-201-50255-0, hereinafter called the Samet Reference.
The most desirable features of a spatial data structure design are: short query time; short data structure update time; and small data structure size. For real time spatial simulations, the first two of these three features are most important. Short query time allows a large number of queries during a simulation step, thereby allowing a larger number of moving 3D objects to be simulated. Data structure update time is also very important because, as an object moves, its location in the spatial data structure is updated. Many data structures (BSP Trees and other presort techniques) provide very high query rates, but have very low data structure update rates. For highest simulation throughput, both fast queries and fast updates are required.
For spatial simulations, example needs for spatial querying are: 1) to determine if moving objects collide; 2) to allow autonomous entities ("virtual creatures") to sense their environment in order to determine behavior; 3) to determine which objects are within the field of view of a human participant as an aid to 3D graphics rendering; and 4) to find constraining surfaces along which an object moves (e.g., tires along a road surface). All of these needs are similar in that they look for objects or surfaces within a specific bounded location within the simulation. For some of the above listed needs, an "object" maybe a region of space (e.g., a viewing frustum or the possible locations of a tire), rather than the representation of an actual 3D object. Hence, the general problem can be thought of as a collision detection problem, and this term will be used throughout the balance of this document.
Ideally, the collision detection problem is solved without requiring the designer of the spatial simulation to make any a priori assumptions about how objects may collide. That is, any object can collide/interact with any other object, and no pairs of objects are assumed to never collide (unless both are stationary). Assuming N objects (all moving) in a simulation, simple algorithms are order N.sup.2. For a simulation with 10,000 objects and 72 simulation steps per second, the number of object-to-object comparisons is 7.2.times.10.sup.11 per second. The simplest object-to-object comparison utilizes a simple bounding volume around each object. Thus, the bounding volumes of objects can first be compared to each other. If the bounding volumes do not intersect, then no further comparisons are required. However, if the bounding volumes intersect, then the actual shape (or a good approximation) of each object must be utilized.
The computational load of object-to-object comparisons whose bounding volumes intersect is dependent on the actual shape of each object. That is, each object is actually a complex surface or volume. The shape of objects can be described by: planar polygons that approximate the surface of an object; Constructive Solid Geometry (CGS) which describes the surface and volume of an object as unions and intersections of simpler geometric primitives; and polyhedra, such as tetrahedrons, which approximate the surface with the faces of the polyhedra and approximate the volume with the volumes of the polyhedra.
Assuming the 3D graphics database of polygons is used for the surface of each object, object surfaces are described by hundreds or thousands of polygons. Thus, when the bounding volumes of two objects intersect, the detailed object-to-object comparison is accomplished by a set of polygon-to-polygon comparisons. Once again, to simplify computations, bounding volumes can be used for each polygon. When the bounding volumes of two polygons intersect, then computational geometry is used to determine if the polygons actually intersect. For CGS and polyhedra representations, a similar approach is used.
Assuming N moving objects, each with M polygons, and a probability p that any two object's bounding volumes intersect, then the total number of bounding volume comparisons needed is N.sup.2 +pM.sup.2 per simulation step. Sophisticated algorithms, such as those in the Melhorn Reference, Gambosi Reference, and the Samet Reference, significantly reduce the number of operations, but generally increase data structure update time. Despite these more sophisticated algorithms, higher performance is needed for sophisticated spatial simulations. This document describes a new method and apparatus for substantially accelerating spatial queries.
Content Addressable Memories
Most Content Addressable Memories (CAM) perform a bit-for-bit equality test between an input vector and each of the data words stored in the CAM. This type of CAM frequently provides masking of bit positions in order to eliminate the corresponding bit in all words from affecting the equality test. It is inefficient to perform magnitude comparisons in a equality-testing CAM because a large number of clock cycles is required to do the task.
CAMs are presently used in translation look-aside buffers within a virtual memory systems in some computers. CAMs are also used to match addresses in high speed computer networks. CAMs are not used in any practical prior art renders.
Magnitude Comparison CAM (MCCAM) is defined here as any CAM where the stored data are treated as numbers, and arithmetic magnitude comparisons (i.e. less-than, greater-than, less-than-or-equal-to, etc.) are performed in parallel. This is in contrast to ordinary CAM which treats stored data strictly as bit vectors, not as numbers. An MCCAM patent, by incorporated herein by reference, is U.S. Pat. No. 4,996,666, by Jerome F. Duluk Jr., entitled "Content-Addressable Memory System Capable of Fully Parallel Magnitude Comparisons", granted Feb. 26, 1991 (hereinafter referred to as the Duluk Patent). Structures within the Duluk Patent specifically referenced shall include the prefix "Duluk Patent", e.g. "Duluk Patent MCCAM Bit Circuit". MCCAMs are not used in any prior art spatial database search apparatuses.
The basic structure of an MCCAM is a set of memory bits organized into words, where each word is composed of one or more fields, where each field stores a number and can perform an arithmetic magnitude comparison between the stored value and input data. In general, one word of prior art MCCAM is used to store the location of one point in a sparsely populated space of points.